package com.leetcode.专项突破.排序算法全解析;

import com.leetcode.common.utils.ArrayUtils;
import java.util.Arrays;

/**
 * @author 覃国强
 * @date 2022-03-02 18:30
 */
public class A01_冒泡排序 {

  public static void main(String[] args) {
    int[] arr = ArrayUtils.randomArr(10);
    System.out.println(Arrays.toString(arr));
    bubbleSort(arr);
    System.out.println(Arrays.toString(arr));
  }

  /**
   * 1. 一边比较一边向后两两交换，将最大值 / 最小值冒泡到最后一位；
   * 2. 经过优化的写法：使用一个变量记录当前轮次的比较是否发生过交换，如果没有发生交换表示已经有序，不再继续排序；
   * 3. 进一步优化的写法：除了使用变量记录当前轮次是否发生交换外，再使用一个变量记录上次发生交换的位置，下一轮排序时到达上次交换的位置就停止比较。
   * @param nums
   */
  public static void bubbleSort(int[] nums) {
    int lastSwapIndex = nums.length - 1;
    while (lastSwapIndex != -1) {
      for (int i = 0; i < nums.length; ++i) {
        int curSwapIndex = -1;
        for (int j = 0; j < lastSwapIndex; ++j) {
          if (nums[j] > nums[j + 1]) {
            swap(nums, j, j + 1);
            curSwapIndex = j;
          }
        }
        lastSwapIndex = curSwapIndex;
      }
    }
  }

  public static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }

}
